|
Bitapアルゴリズム（）とは、ビット演算の並列性を利用した文字列探索アルゴリズムである。Baeza–Yates–Gonnetアルゴリズムや、Shift-andアルゴリズム・Shift-orアルゴリズムとも呼ばれる（andとorがあるのは、ブール代数の双対性にもとづくバリエーションである）。レーベンシュタイン距離などの編集距離に基づく「似た」文字列を見つけ出すに利用できることが、他の文字列探索アルゴリズムにない特徴である。以下、Shift-and型を前提に説明する。 このアルゴリズムの基本的な考え方は1964年にBálint Dömölkiによって紹介された。1977年にR. K. Shyamasundarによって拡張された。 Ricardo Baeza-Yates、Gaston Gonnetらの成果をもとに1991年、Wu、Manberらによってあいまい検索へ適用可能であることが示された のち、1996年にBaeza-Yates、Navarroらによって効率化され、1998年にEugene Myersによって長いパターンへ適用する方法が示された。 bitapという名前については、agrepの添付文書agrep.chronicleの中に「Feb/91: The approximate pattern matching algorithm called 'bitap' (bit-parallel approximate pattern matching) is designed. The algorithm is a generalization of Baeza-Yates' "shift-or" algorithm for exact matching.」と書かれている。よって厳密には、あいまい検索に拡張したアルゴリズムに限定してbitapあるいはWuとManberのアルゴリズムとし、それ以外の名前はそれ以外のアルゴリズムも含む総称とすべきかもしれないが、通常特に区別されていない。 == アルゴリズム == このアルゴリズムはマッチさせるパターンの状態遷移を表す決定性有限オートマトン(DFA)をエミュレートする。1つの立っている（shift-orなら降りている）ビットが1つの非決定性有限オートマトン(NFA)に対応し、またその立っている位置が該NFAの状態を示している。これ等複数のNFAの状態を同時管理した一つの整数がDFAの状態となっている。そしてこれ等各々のNFAの状態遷移を連接のみに限ることにより一回のシフト動作で全てのNFAの状態遷移を同時に行なえ、また同様にアトムを文字クラスのみに限ることにより一回のマスク動作で必要な全てのNFAの拒否(reject)を行なえるアルゴリズムとなっている。 （→#正規表現との関係） 例として対象の文字列T=acb''acbaca'',パターン文字列P=''acbaca''を考える。以下に示す表は横軸にT、縦軸にPを配置し、どのように遷移するかを示すものである。初期状態でRはすべて0で初期化される。 この表で例えばR6=001000からR7=100100への遷移はR6を1ビット右にシフトしたもの(000100)とcに当たるビットマスク(100100)とのビット単位でのANDを取った値に等しい。 こうして最上位ビットに1がたったとき、それまでの経路がマッチした文字列だと言える。バックトラックが不要なため、パターンに似た配列が含まれるときに高速に動作できる。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Bitapアルゴリズム」の詳細全文を読む 英語版ウィキペディアに対照対訳語「 Bitap algorithm 」があります。 スポンサード リンク
|